|
In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for numbering permutations and is an example of an inversion table. The Lehmer code is named in reference to Derrick Henry Lehmer,〔 but the code had been known since 1888 at least.〔 ==The code== The Lehmer code makes use of the fact that there are : permutations of a sequence of ''n'' numbers. If a permutation ''σ'' is specified by the sequence (''σ''1, …, ''σ''''n'') of its images of 1, …, ''n'', then it is encoded by a sequence of ''n'' numbers, but not all such sequences are valid since every number must be used only once. By contrast the encodings considered here choose the first number from a set of ''n'' values, the next number from a fixed set of values, and so forth decreasing the number of possibilities until the last number for which only a single fixed value is allowed; ''every'' sequence of numbers chosen from these sets encodes a single permutation. While several encodings can be defined, the Lehmer code has several additional useful properties; it is the sequence : in other words the term ''L''(''σ'')''i'' counts the number of terms in (''σ''1, …, ''σ''''n'') to the right of ''σ''''i'' that are smaller than it, a number between 0 and , allowing for different values. A pair of indices (''i'',''j'') with and is called an inversion of ''σ'', and ''L''(''σ'')''i'' counts the number of inversions (''i'',''j'') with ''i'' fixed and varying ''j''. It follows that is the total number of inversions of ''σ'', which is also the number of adjacent transpositions that are needed to transform the permutation into the identity permutation. Other properties of the Lehmer code include that the lexicographical order of the encodings of two permutations is the same as that of their sequences (''σ''1, …, ''σ''''n''), that any value 0 in the code represents a right-to-left minimum in the permutation (i.e., a smaller than any to its right), and a value at position ''i'' similarly signifies a right-to-left maximum, and that the Lehmer code of ''σ'' coincides with the factorial number system representation of its position in the list of permutations of ''n'' in lexicographical order (numbering the positions starting from 0). Variations of this encoding can be obtained by counting inversions (''i'',''j'') for fixed ''j'' rather than fixed ''i'', by counting inversions with a fixed smaller ''value'' rather than smaller index ''i'', or by counting non-inversions rather than inversions; while this does not produce a fundamentally different type of encoding, some properties of the encoding will change correspondingly. In particular counting inversions with a fixed smaller value gives the inversion table of ''σ'', which can be seen to be the Lehmer code of the inverse permutation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lehmer code」の詳細全文を読む スポンサード リンク
|